package 牛客.二叉树;

import 剑指offer.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class BM34判断是不是二叉搜索树 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        //BST二叉搜索树：当前根节点大于左子树，小于右子树
        //树形dp套路
        return fun(root).isBst;
    }

    public static class returnData {
        public boolean isBst;
        public int min;
        public int max;

        public returnData(boolean isBst, int min, int max) {
            this.isBst = isBst;
            this.min = min;
            this.max = max;
        }
    }

    private returnData fun(TreeNode root) {
        if (root==null) {
            return null;
        }

        returnData leftData=fun(root.left);
        returnData rightData=fun(root.right);

        //确定当前根节点的returnData.min 和  returnData.max
        int min=root.val;
        int max=root.val;
        if (leftData!=null) {
            min=Math.min(min,leftData.min);
            max=Math.max(max,leftData.max);
        }
        if (rightData!=null) {
            min=Math.min(min,rightData.min);
            max=Math.max(max,rightData.max);
        }

        //确定 returnData.isBst
        boolean isBst=true;
        if (leftData!=null && (!leftData.isBst || root.val<=leftData.max)){
            //违背BST的规则，就设为false
            isBst=false;
        }
        if (rightData!=null && (!rightData.isBst || root.val>=rightData.min)){
            isBst=false;
        }

        return new returnData(isBst,min,max);
    }


    private static int preValue=Integer.MIN_VALUE;
    public boolean isValidBST2 (TreeNode root) {
        if (root==null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val > preValue) {
            preValue=root.val;
        }else {
            return false;
        }

        return isValidBST(root.right);
    }


    public boolean isValidBST1 (TreeNode root) {
        //二叉搜索树 它的根节点大于左孩子，小于右孩子：中序遍历结果有序
        //非递归实现
        // write code here
        List<TreeNode> list=new ArrayList<>();
        inorder(root,list);

        boolean res=true;
        for (int i = 0; i < list.size()-1; i++) {
            if (list.get(i).val<list.get(i+1).val) {
                continue;
            }else {
                return false;
            }
        }
        return res;

    }

    private void inorder(TreeNode root, List<TreeNode> list) {
        //中序遍历
        if (root==null) {
            return;
        }

        inorder(root.left,list);
        list.add(root);
        inorder(root.right,list);
    }
}
